#include <limits.h>  // INT_MIN,INT_MAX
#include <math.h>    // abs,pow

#include <algorithm>      // sort
#include <iostream>       // cout,cin
#include <numeric>        // accumulate
#include <string>         // string
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <vector>         // vector

using namespace std;

// 如果x是2的幂则返回True，否则返回False
bool IsPowerOf2(int x) { return (x & (x - 1)) == 0; }

class Solution {
   public:
    int countSubstrings(string s) {
        // 将s的长度修改为偶数，在首尾添加不同字符保证循环结束
        string t = "$#";
        for (const char &c : s) {
            t += c;
            t += "#";
        }
        t += "?";

        int n = t.size() - 1;

        vector<int> f(n);

        int ans = 0;

        int iMax = 0;  // 最长回文子串的中心点位置
        int rMax = 0;  // 最长回文子串的右端点位置

        for (int i = 1; i < n; i++) {
            // 初始化 f[i]
            if (i < rMax) {
                f[i] = min(rMax - i + 1, f[2 * iMax - i]);
            } else {
                f[i] = 1;
            }

            // 中心扩展
            while (t[i + f[i]] == t[i - f[i]]) {
                f[i]++;
            }

            // 维护iMax和rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }

            // 计算答案(因为之前已将字符串改为偶数长度)
            ans += (f[i] / 2);
        }

        return ans;
    }
};

int main() {
    Solution solution;
    return 0;
}